
//leetcode submit region begin(Prohibit modification and deletion)
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    /**
     * 第一遍：递归思想
     * @param head
     * @return
     */
//    public ListNode swapPairs(ListNode head) {
//        if (head == null || head.next == null) return null;
//
//        ListNode slow = head, fast = head.next, other = head.next.next;
//        fast.next = slow;
//        // swapPairs：两两交换
//        slow.next = swapPairs(other);
//        return fast;
//    }


    /**
     * 第二遍 2/24
     * @param head
     * @return
     */
//    public ListNode swapPairs(ListNode head) {
//        if (head == null || head.next == null) return head;
//        ListNode slow = head, fast = head.next, other = head.next.next;
//        fast.next = slow;
//        slow.next = swapPairs(other);
//        return fast;
//    }


    /**
     * 第三遍 2/27
     * 三指针；迭代
     * @param head
     * @return
     */
//    public ListNode swapPairs(ListNode head) {
//        if (head == null || head.next == null) return head;
//
//        ListNode slow = head, fast = head.next, other = head.next.next;
//        fast.next = slow;
//        slow.next = swapPairs(other);
//        return fast;
//    }


    /**
     * 第四遍 3/7
     * @param head
     * @return
     */
    public ListNode swapPairs(ListNode head) {
        if (head == null || head.next == null) return head;

        ListNode slow = head, fast = head.next, other = head.next.next;
        fast.next = slow;
        slow.next = swapPairs(other);
        return fast;
    }
}
//leetcode submit region end(Prohibit modification and deletion)
